import java.lang.Iterable;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * A double-ended queue or deque (pronounced "deck") is a generalization of a stack
 * and a queue that supports inserting
 * and removing items from either the front or the back of the data structure.
 */
public class Deque<Item> implements Iterable<Item> {

    private static class Node<Item> {
        Item item;
        Node<Item> next;

        private Node(Item item) {
            this.item = item;
        }
    }

    Node<Item> first, last;


    /**
     * construct an empty deque
     */
    public Deque() {
    }

    /**
     * is the deque empty?
     */
    public boolean isEmpty() {
        return true;
    }

    /**
     * return the number of items on the deque
     */
    public int size() {
        return 0;
    }

    /**
     * insert the item at the front
     */
    public void addFirst(Item item) {
        if (item == null)
            throw new NullPointerException();
    }

    /**
     * insert the item at the end
     */
    public void addLast(Item item) {
        if (item == null)
            throw new NullPointerException();
    }

    /**
     * delete and return the item at the front
     */
    public Item removeFirst() {
        if (isEmpty())
            throw new NoSuchElementException();

        return null;
    }

    /**
     * delete and return the item at the end
     */
    public Item removeLast() {
        if (isEmpty())
            throw new NoSuchElementException();

        return null;
    }

    /**
     * return an iterator over items in order from front to end
     */
    public Iterator<Item> iterator() {
        return null;
    }
}

